#include "GaloisFieldPolynomial.h"

namespace galois
{

   GaloisFieldPolynomial::GaloisFieldPolynomial(GaloisField* _gf)
   {
      gf = _gf;
      poly.clear();
   }

   GaloisFieldPolynomial::GaloisFieldPolynomial(GaloisField* _gf, unsigned int size, GaloisFieldElement* gfe)
   {
     unsigned int i;

      if (size > 0)
      {
         gf = _gf;
	 poly.resize(size+1);

         if (gfe != NULL)
         {
            for(i = 0; i <= size; i++)
            {
               poly[i] = gfe[i];
            }
         }
         else
         {
            for(i = 0; i < poly.size(); i++)
            {
               poly[i] = GaloisFieldElement(gf,0);
            }
         }
      }
      else
      {
         gf = NULL;
         poly.clear();
      }
   }


   GaloisFieldPolynomial::GaloisFieldPolynomial(const GaloisFieldPolynomial& gfp)
   {
      gf   = gfp.gf;
      poly = gfp.poly;
   }

   GaloisFieldPolynomial::GaloisFieldPolynomial(const GaloisFieldElement& gfe)
   {
      gf = gfe.field();
      poly.clear();
      poly.push_back(gfe);
   }


   bool GaloisFieldPolynomial::valid() const
   {
      return (poly.size() > 0);
   }


   unsigned int GaloisFieldPolynomial::deg() const
   {
      return (poly.size()-1);
   }


   GaloisField* GaloisFieldPolynomial::field() const
   {
      return gf;
   }

   void GaloisFieldPolynomial::set_degree(const unsigned int& x)
   {
#if 0 // Looks like a bug
      poly.resize(x - 1,GaloisFieldElement(gf,0));
#else
      poly.resize(x + 1,GaloisFieldElement(gf,0));
#endif
   }


   GaloisFieldPolynomial& GaloisFieldPolynomial::operator=(const GaloisFieldPolynomial& gfp)
   {
      if (this == &gfp)
        return *this;

      gf   = gfp.gf;
      poly = gfp.poly;

      return *this;
   }


   GaloisFieldPolynomial& GaloisFieldPolynomial::operator=(const GaloisFieldElement& gfe)
   {
      poly.clear();
      gf = gfe.field();
      poly.push_back(gfe);
      return *this;
   }


   GaloisFieldPolynomial& GaloisFieldPolynomial::operator=(const GFSymbol& gfs)
   {
      GaloisFieldElement gfe(gf, gfs);
      *this = gfe;
      return *this;
   }


   GaloisFieldPolynomial& GaloisFieldPolynomial::operator+=(const GaloisFieldPolynomial& gfp)
   {
     unsigned int i, j;

      if (gf == gfp.gf)
      {

         if (poly.size() < gfp.poly.size())
         {
            j = 0;
            for (i = 0; i < poly.size(); i++)
            {
               poly[i] += gfp.poly[j++];
            }

            for ( ; j < gfp.poly.size(); j++)
            {
               poly.push_back(gfp.poly[j]);
            }
         }
         else
         {
            i = 0;
            for (j = 0; j < gfp.poly.size(); j++)
            {
               poly[i++] += gfp.poly[j];
            }
         }


         simplify(*this);

      }

      return *this;
   }


   GaloisFieldPolynomial& GaloisFieldPolynomial::operator+=(const GaloisFieldElement& gfe)
   {
      poly[0] += gfe;
      return *this;
   }


   GaloisFieldPolynomial& GaloisFieldPolynomial::operator-=(const GaloisFieldPolynomial& gfe)
   {
      return (*this += gfe);
   }


   GaloisFieldPolynomial& GaloisFieldPolynomial::operator-=(const GaloisFieldElement& gfe)
   {
      poly[0] -= gfe;
      return *this;
   }


   GaloisFieldPolynomial& GaloisFieldPolynomial::operator*=(const GaloisFieldPolynomial& gfp)
   {
     unsigned int i,j;

      if (gf == gfp.gf)
      {
         GaloisFieldPolynomial product(gf,deg() + gfp.deg() + 1);

         for (i= 0; i < poly.size(); i++)
         {
            for (j = 0; j < gfp.poly.size(); j++)
            {
               product.poly[i+j] += poly[i] * gfp.poly[j];
            }
         }

         simplify (product);
         poly = product.poly;
      }
      return *this;
   }


   GaloisFieldPolynomial& GaloisFieldPolynomial::operator*=(const GaloisFieldElement& gfe)
   {
     unsigned int i;

      if (gf == gfe.field())
      {
         for(i = 0; i < poly.size(); i++)
         {
            poly[i] *= gfe;
         }
      }
      return *this;
   }


   GaloisFieldPolynomial& GaloisFieldPolynomial::operator/=(const GaloisFieldPolynomial& gfp)
   {
      if ((gf == gfp.gf) &&
          (deg() >= gfp.deg()) &&
          (gfp.deg() >= 0)
         )
      {

         GaloisFieldPolynomial quotent(gf, deg() - gfp.deg() + 1);
         GaloisFieldPolynomial remainder(gf, gfp.deg() - 1);

	 int i;
         for(i = deg(); i >= 0; i--)
         {

            if (i <= (int)quotent.deg())
              quotent[i] = remainder[remainder.deg()] / gfp[gfp.deg()];

	    int j;
            for(j = remainder.deg(); j > 0; j--)
            {
               remainder[j] = remainder[j - 1] + (quotent[i] * gfp[j]);
            }

            remainder[0] = poly[i] + (quotent[i] * gfp[0]);

         }

         simplify(quotent);

         poly = quotent.poly;

      }

      return *this;
   }


   GaloisFieldPolynomial& GaloisFieldPolynomial::operator/=(const GaloisFieldElement& gfe)
   {
     unsigned int i;

      if (gf == gfe.field())
      {
         for (i = 0;  i < poly.size(); i++)
         {
            poly[i] /= gfe;
         }
      }
      return *this;
   }


   GaloisFieldPolynomial& GaloisFieldPolynomial::operator%=(const GaloisFieldPolynomial& gfp)
   {

      if ((gf == gfp.gf) &&
          (deg() >= gfp.deg()) &&
          (gfp.deg() >= 0)
         )
      {

         GaloisFieldPolynomial quotent(gf, deg() - gfp.deg() + 1);
         GaloisFieldPolynomial remainder(gf, gfp.deg() - 1);


	 int i;
         for(i = deg(); i >= 0; i--)
         {

            if (i <= (int)quotent.deg())
              quotent[i] = remainder[remainder.deg()] / gfp[gfp.deg()];

	    int j;
            for(j = remainder.deg(); j > 0; j--)
            {
               remainder[j] = remainder[j - 1] + (quotent[i] * gfp[j]);
            }

            remainder[0] = poly[i] + (quotent[i] * gfp[0]);

         }

         simplify(remainder);

         poly = remainder.poly;
		 

      }




      return *this;

   }


   GaloisFieldPolynomial& GaloisFieldPolynomial::operator%=(const unsigned int& power)
   {
      if (poly.size() >= power)
        poly.resize(power);
      simplify(*this);
      return *this;
   }


   GaloisFieldPolynomial& GaloisFieldPolynomial::operator^=(const int& n)
   {
      GaloisFieldPolynomial result = *this;

      int i;
      for (i = 0; i < n; i++)
      {
         result *= *this;
      }

      *this = result;

      return *this;
   }


   GaloisFieldPolynomial& GaloisFieldPolynomial::operator<<=(const unsigned int& n)
   {
     int i;
     unsigned int ui;
      if (poly.size() > 0)
      {
         int initial_size = poly.size();
         poly.resize(poly.size() + n,GaloisFieldElement(gf,0));

         for(i = initial_size - 1; i >= 0; i--)
         {
            poly[i + n] = poly[i];
         }

         for(ui = 0; ui < n; ui++)
         {
            poly[ui] = 0;
         }
      }

      return *this;
   }


   GaloisFieldPolynomial& GaloisFieldPolynomial::operator>>=(const unsigned int& n)
   {
     unsigned int i;
      if (n  < deg()+1)
      {
#if 0
	// Looks like a bug
         for(i = 0;  i < (n + 1); i++)
#else
	   // Should includde this code for bug fix
         for(i = 0;  i < n; i++)
#endif
         {
			 if ((i+n) >= poly.size()) {
				 printf("poly.size: %d\n", poly.size());
				 printf("i+n: %d\n", i+n);
				 printf("\n\n(i+n) > poly.size()\n\n");
#if 1 // Looks like a bug without this
				 poly[i] = 0;
#endif
			 }
			 else {
				 poly[i] = poly[i + n];
			 }
         }

         poly.resize(poly.size() - n,GaloisFieldElement(gf,0));

      }

      return *this;
   }


   const GaloisFieldElement& GaloisFieldPolynomial::operator[](const unsigned int& term) const
   {
      if (term < poly.size())
        return poly[term];
      else
       return poly[0];
   }


   GaloisFieldElement& GaloisFieldPolynomial::operator[](const unsigned int& term)
   {
      if (term < poly.size())
        return poly[term];
      else
       return poly[0];
   }


   GaloisFieldElement GaloisFieldPolynomial::operator()(const GaloisFieldElement& value)
   {
      GaloisFieldElement result(gf,0);

      if (poly.size() > 0)
      {
        result = poly[poly.size()-1];
	int i;
        for(i = poly.size() - 2; i >= 0; i--)
        {
           result = poly[i] + (result * value);
        }
      }
      return result;
   }


   GaloisFieldElement GaloisFieldPolynomial::operator()(GFSymbol value)
   {
      return (*this)(GaloisFieldElement(gf,value));
   }


   bool GaloisFieldPolynomial::operator==(const GaloisFieldPolynomial& gfp) const
   {
     unsigned int i;

      if (gf == gfp.gf)
      {
         if (poly.size() != gfp.poly.size())
          return false;
         else
         {
            for (i = 0; i < poly.size(); i++)
            {
               if (poly[i] != gfp.poly[i])
                 return false;
            }
            return true;
         }
      }
      else
        return false;
   }


   bool GaloisFieldPolynomial::operator!=(const GaloisFieldPolynomial& gfp) const
   {
      return !(*this == gfp);
   }


   GaloisFieldPolynomial GaloisFieldPolynomial::derivative()
   {
     unsigned int i;

      if ((*this).poly.size() > 1)
      {
         GaloisFieldPolynomial deriv(gf,deg());
         for (i = 0; i < poly.size() - 1; i++)
         {
            if (((i + 1) & 1) == 1)
               deriv.poly[i] = poly[i + 1];
            else
              deriv.poly[i] = 0;
            //poly[i] = (((i + 1) & 1 == 1) ? poly[i + 1] : GaloisFieldElement(gf,0));   // Note: something weird happens when you use this line.
         }
         simplify(deriv);
         return deriv;
     }
     return GaloisFieldPolynomial(gf,0);
   }


   void GaloisFieldPolynomial::simplify()
   {
      simplify(*this);
   }


   void GaloisFieldPolynomial::simplify(GaloisFieldPolynomial& gfp)
   {
     if (gfp.poly.size()) {
       int last = gfp.poly.size() - 1;

       if  (gfp.poly[last] == 0) {
	 while(last >= 0)
	   {
	     if (gfp.poly[last] != 0)
	       break;

	     last--;
	   }
	 gfp.poly.resize(last+1);
       }
     }
   }


   GaloisFieldPolynomial operator+(const GaloisFieldPolynomial& a, const GaloisFieldPolynomial& b)
   {
      GaloisFieldPolynomial result = a;
      result += b;
      return result;
   }


   GaloisFieldPolynomial operator + (const GaloisFieldPolynomial& a, const GaloisFieldElement& b)
   {
      GaloisFieldPolynomial result = a;
      result += b;
      return result;
   }


   GaloisFieldPolynomial operator + (const GaloisFieldElement& a, const GaloisFieldPolynomial& b)
   {
      GaloisFieldPolynomial result = b;
      result += a;
      return result;
   }


   GaloisFieldPolynomial operator + (const GaloisFieldPolynomial& a, const GFSymbol& b)
   {
      return a + GaloisFieldElement(a.field(),b);
   }


   GaloisFieldPolynomial operator + (const GFSymbol& a, const GaloisFieldPolynomial& b)
   {
      return b + GaloisFieldElement(b.field(),a);
   }


   GaloisFieldPolynomial operator-(const GaloisFieldPolynomial& a, const GaloisFieldPolynomial& b)
   {
      GaloisFieldPolynomial result = a;
      result -= b;
      return result;
   }

   GaloisFieldPolynomial operator - (const GaloisFieldPolynomial& a, const GaloisFieldElement& b)
   {
      GaloisFieldPolynomial result = a;
      result -= b;
      return result;
   }


   GaloisFieldPolynomial operator - (const GaloisFieldElement& a, const GaloisFieldPolynomial& b)
   {
      GaloisFieldPolynomial result = b;
      result -= a;
      return result;
   }


   GaloisFieldPolynomial operator - (const GaloisFieldPolynomial& a, const GFSymbol& b)
   {
      return a - GaloisFieldElement(a.field(),b);
   }


   GaloisFieldPolynomial operator - (const GFSymbol& a, const GaloisFieldPolynomial& b)
   {
      return b - GaloisFieldElement(b.field(),a);
   }


   GaloisFieldPolynomial operator*(const GaloisFieldPolynomial& a, const GaloisFieldPolynomial& b)
   {
      GaloisFieldPolynomial result = a;
      result *= b;
      return result;
   }


   GaloisFieldPolynomial operator*(const GaloisFieldElement& a, const GaloisFieldPolynomial& b)
   {
      GaloisFieldPolynomial result = b;
      result *= a;
      return result;
   }


   GaloisFieldPolynomial operator*(const GaloisFieldPolynomial& a, const GaloisFieldElement& b)
   {
      GaloisFieldPolynomial result = a;
      result *= b;
      return result;
   }

   GaloisFieldPolynomial operator/(const GaloisFieldPolynomial& a, const GaloisFieldPolynomial& b)
   {
      GaloisFieldPolynomial result = a;
      result /= b;
      return result;
   }


   GaloisFieldPolynomial operator/(const GaloisFieldPolynomial& a, const GaloisFieldElement& b)
   {
      GaloisFieldPolynomial result = a;
      result /= b;
      return result;
   }


   GaloisFieldPolynomial operator%(const GaloisFieldPolynomial& a, const GaloisFieldPolynomial& b)
   {
      GaloisFieldPolynomial result = a;
      result %= b;
      return result;
   }

   GaloisFieldPolynomial operator%(const GaloisFieldPolynomial& a, const unsigned int& power)
   {
      GaloisFieldPolynomial result = a;
      result %= power;
      return result;
   }

   GaloisFieldPolynomial operator^(const GaloisFieldPolynomial& a, const int& n)
   {
      GaloisFieldPolynomial result = a;
      result ^= n;
      return result;
   }


   GaloisFieldPolynomial operator<<(const GaloisFieldPolynomial& a, const unsigned int& n)
   {
      GaloisFieldPolynomial result = a;
      result <<= n;
      return result;
   }


   GaloisFieldPolynomial operator>>(const GaloisFieldPolynomial& a, const unsigned int& n)
   {
      GaloisFieldPolynomial result = a;
      result >>= n;
      return result;
   }


   GaloisFieldPolynomial gcd(const GaloisFieldPolynomial& a, const GaloisFieldPolynomial& b)
   {
      if (a == b)
      {
         if (!a.valid() == 0)
           return b;

         if (!b.valid() == 0)
           return a;

         GaloisFieldPolynomial x = a % b;
         GaloisFieldPolynomial y = b;
         GaloisFieldPolynomial z = x;

         while ((z = y % x).valid())
         {
            y = x;
            x = z;
         }
         return x;
      }
      return GaloisFieldPolynomial();
   }


   ostream& operator << (ostream& os, const GaloisFieldPolynomial& gfp)
   {

     unsigned int i;

      if (gfp.deg() >= 0)
      {

         for (i = 0; i < gfp.poly.size(); i++)
         {
            os << gfp.poly[i].index()
               << ((i != (gfp.deg())) ? " " : "");
               //<< "x^"
               //<< i
               //<< ((i != (gfp.deg())) ? " + " : "");
         }


         cout << "       poly form: ";

         for (i = 0; i < gfp.poly.size(); i++)
         {
            os << gfp.poly[i].poly()
               << ((i != (gfp.deg())) ? " " : "");
               //<< "x^"
               //<< i
               //<< ((i != (gfp.deg())) ? " + " : "");
         }


      }

      return os;
   }

}


